package algorithm.MonotonePriorityStack.leetcode_739;

import java.util.Stack;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int [] ans = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i =0 ; i < n; i++) {
            while(!stack.isEmpty()&&temperatures[stack.peek()]<=temperatures[i]){
                int temp = stack.pop();
                ans[temp] = i;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int temp = stack.pop();
            ans[temp] = -1;
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ans[i] != -1 && temperatures[ans[i]] == temperatures[i]) {
                ans[i] = ans[ans[i]];
            }
        }
        for (int i = 0; i < n; i++) {
            if (ans[i] == -1) {
                ans[i]  = 0;
            }
            else {
                ans[i] = ans[i] - i;
            }
        }
        return ans;
    }
}